#include <bits/stdc++.h>

constexpr int P = 1e9 + 7;

int k;
int a[64], b[64];

int f[64][2][2][2][2]; // [p][0?][i < n][j < m][j < i]

int dp(int p, bool f0, bool fn, bool fm, bool fij) {
    if (p == -1) return int(f0);
    int &res = f[p][f0][fn][fm][fij];
    if (res != -1) return res;
    res = 0;
    int upn = fn ? k - 1 : a[p];
    int upm = fm ? k - 1 : b[p];
    for (int i = 0; i <= upn; ++i) {
        for (int j = 0; (fij || j <= i) && j <= upm; ++j) {
            res = (res + dp(p - 1, f0 || (i < j), fn || (i < a[p]), fm || (j < b[p]), fij || (j < i))) % P;
        }
    }
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T;
    std::cin >> T >> k;
    while (T--) {
        std::fill(a, a + 64, 0);
        std::fill(b, b + 64, 0);
        std::fill_n(f[0][0][0][0], sizeof(f) / sizeof(int), -1);

        long long n, m;
        std::cin >> n >> m;
        int cn = 0;
        while (n) {
            a[cn++] = n % k;
            n /= k;
        }
        int cm = 0;
        while (m) {
            b[cm++] = m % k;
            m /= k;
        }
        std::cout << dp(std::max(cn, cm) - 1, false, false, false, false) << '\n';
    }

    return 0;
}